#ifndef SKIPLIST_H
#define SKIPLIST_H

#include <cstddef>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <ctime>


const int MAX_LEVEL = 16;
const float P = 0.5;

template<typename K, typename V>
class SkipListNode{
public:
    K key;
    V value;
    std::vector<SkipListNode<K, V>*> forward;

    SkipListNode(K k, V v, int level) : key(k), value(v), forward(level, nullptr){}
};

template<typename K, typename V>
class SkipList{
public:
    SkipList();
    ~SkipList();
    bool insert(K key, V value);
    bool remove(K key);
    bool search(K key, V& value);
    void display();

private:
    int randomLevel();
    SkipListNode<K,V>* head;
    int level;
};

template<typename K, typename V>
SkipList<K, V>::SkipList(){
    level = 1;
    head = new SkipListNode<K, V>(K(), V(), MAX_LEVEL);
    std::srand(std::time(nullptr));
}

template<typename K, typename V>
SkipList<K, V>::~SkipList(){
    SkipListNode<K, V>* x = head;
    while (x) {
        SkipListNode<K, V>* next = x->forward[0];
        delete x;
        x = next;
    }
}

template<typename K, typename V>
int SkipList<K, V>::randomLevel(){
    int lvl = 1;
    while (((float)std::rand() / RAND_MAX) < P && lvl < MAX_LEVEL) {
        lvl++;
    }
    return lvl;
}

template<typename K, typename V>
bool SkipList<K, V>::insert(K key, V value){
    std::vector<SkipListNode<K, V>*> update(MAX_LEVEL, nullptr);
    SkipListNode<K, V>* x = head;

    for (int i = level - 1; i >= 0; i--) {
        while (x->forward[i] && x->forward[i]->key < key) {
            x = x->forward[i];
        }
        update[i] = x;
    }
    x = x->forward[0];

    if (x && x->key == key) {
        x->value = value;
        return false;
    }

    int new_level = randomLevel();
    if (new_level > level) {
        for (int i = level; i < new_level; i++) {
            update[i] = head;
        }
        level = new_level;
    }

    x = new SkipListNode<K, V>(key, value, new_level);
    for (int i = 0; i < new_level; i++) {
        x->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = x;
    }
    return true;
}

template<typename K, typename V>
bool SkipList<K, V>::remove(K key){
    std::vector<SkipListNode<K, V>*> update(MAX_LEVEL,nullptr);
    SkipListNode<K, V>* x = head;

    for (int i = level - 1; i >= 0; i--) {
        while (x->forward[i] && x->forward[i]->key < key) {
            x = x->forward[i];
        }
        update[i] = x;
    }
    x = x->forward[0];

    if (!x || x->key != key) {
        return false;
    }

    for (int i = 0; i < level; i++) {
        if (update[i]->forward[i] != x) {
            break;
        }
        update[i]->forward[i] = x->forward[i];
    }

    delete x;

    while (level > 1 && head->forward[level - 1] == nullptr) {
        level--;
    }

    return true;
}

template<typename K, typename V>
bool SkipList<K, V>::search(K key, V& value){
    SkipListNode<K, V>* x = head;
    for (int i = level - 1; i >= 0; i--) {
        while (x->forward[i] && x->forward[i]->key < key) {
            x = x->forward[i];
        }
    }
    x = x->forward[0];
    if (x && x->key == key) {
        value = x->value;
        return true;
    }
    return false;
}

template<typename K, typename V>
void SkipList<K, V>::display(){
    std::cout << "\n***** Skip List *****" << std::endl;
    for (int i = level - 1; i>= 0; i--) {
        SkipListNode<K, V>* x = head->forward[i];
        std::cout << "Level " << i + 1<< ": ";
        while (!x) {
            std::cout << x->key << "," << x->value << "  ";
            x = x->forward[i];
        }
        std::cout << std::endl;
    }
}

#endif